Xuyên suốt năm 1993, Carey bắt đầu lên ý tưởng cho Music Box , sau đó trở thành album bán chạy nhất trong sự nghiệp của nữ ca sĩ.[2] Đối với hai album trước đó, sự sáng tạo của Carey phải chịu kiểm soát nặng nề đến từ hãng đĩa của mình Columbia Records, cũng như từ người chồng kiêm giám đốc công ty, Tommy Mottola.[2] Những nỗ lực trước đó của cô, Emotions (1991), tìm lại những ảnh hưởng âm nhạc của các thập niên 1950s, 60s, và nhạc balldad 70s , gospel, R&B và soul, tuy nhiên đã thất bại trong việc tạo dựng thành công tương tự như album đầu tay.[2] Xuất phát từ thành tích thương mại nghèo nàn của Emotions, hãng Columbia đã định hướng cho Music Box trở thành phương tiện thúc đẩy lượt nghe radio airplay cực lớn cho từng đĩa đơn một.[3] Album được định hình theo chất liệu nhạc pop, và đi theo xu hướng triệt để hơn tất cả những gì mà Emotions đã làm được. Music Box bán được 32 triệu bản trên toàn thế giới, và chiếm một vị trí trong danh sách những album bán chạy nhất mọi thời đại.[4][5] Từ những thành công đó, Columbia đã cho phép Carey được quyền kiểm soát nhiều hơn chất nhạc mà cô thu âm cho Daydream (1995).[2]

Trước khi Carey tìm ra hướng đi mà mình muốn áp đặt cho album, cô đã hình thành nên ý tưởng và giai điệu cho "Underneath the Stars," và nhận ra rằng nó sẽ phù hợp với album bất chấp âm thanh của bài hát sẽ như thế nào.[3] Như vậy, "Underneath the Stars" đã trở thành bài hát đầu tiên mà Carey viết và thu âm cho album, đồng thời cũng xem như là sự tri ân cho dòng nhạc đã gắn liền với sự trưởng thành của bản thân, cũng như giọng ca truyền cảm hứng, Minnie Riperton.[3] "Underneath the Stars" cuối cùng được chọn làm đĩa đơn thứ 6 cho album, được phát hành ngày 5 tháng 4 năm 1996 thông qua Columbia Records.[3] Ở Úc, bài hát là đĩa B-side cho, "Forever" (1996).[6]